package primary.primary0;

import java.util.*;

/**
 *
 *
 *
 * 答案里的key还是Integer，个人感觉这个东西用来当key，拆装箱会很麻烦
 * mark: integer的==和equals,equals是直接比较val的，所以不用考虑拆装箱，即使是 Integer.valueOf(1).equals(1)也是true
 * == 在 -128 ~ 127 之间的可以，超过了就不行。 比如Integer.valueOf(1000).equals(1000)返回false。
 * true        System.out.println(Integer.valueOf(1000).equals(1000));
 * true        System.out.println(Integer.valueOf(1000) == 1000);
 * true        System.out.println(1000 == Integer.valueOf(1000));
 * false        System.out.println(Integer.valueOf(1000) == Integer.valueOf(1000));
 */
public class S0146LRU缓存 {

    /**
     * 41，自己又写了一版，感觉不错，这一版好记的
     */
    class LRUCache6 {

        class Node{
            // mark:注意key和value都要放进去，方便取值
            int key;
            int value;
            Node pre;
            Node next;
            Node(int _key, int _value){
                key = _key;
                value = _value;
            }
            Node(){

            }
        }
        Node head;
        Node tail;
        int capacity;
        Map<Integer, Node> record = new HashMap<>();

        public LRUCache6(int capacity) {
            this.capacity = capacity;
            head = new Node();
            tail = new Node();
            head.next = tail;
            tail.pre = head;
        }

        public int get(int key) {
            if(record.containsKey(key)){
                Node node = record.get(key);
                afterAccess(node);
                return node.value;
            }else{
                return -1;
            }
        }

        public void put(int key, int value) {
            if(record.containsKey(key)){
                // 存在，需要覆盖
                Node oldNode = record.get(key);
                oldNode.value = value;
                afterAccess(oldNode);
            }else{
                Node node = new Node(key, value);
                record.put(key, node);
                afterInsert(node);
                if(record.size() > capacity){
                    Node toRemove = tail.pre;
                    record.remove(toRemove.key);
                    afterRemove(toRemove);
                }
            }
        }

        // 这里仿照LinkedHashMap的三个扩展方法做的，这里三个方法只处理链表操作，不管map操作。
        private void afterAccess(Node node){
            // 访问后，移到前面
            // 1. 删除原位置
            Node pre = node.pre;
            Node next = node.next;
            pre.next = next;
            next.pre = pre;
            // 2. 前面插入
            Node newNext = head.next;
            head.next = node;
            node.pre = head;
            node.next = newNext;
            newNext.pre = node;
        }
        // afterInsert和afterRemove 可以直接从afterAccess里面复制，很方便
        private void afterInsert(Node node){
            Node newNext = head.next;
            head.next = node;
            node.pre = head;
            node.next = newNext;
            newNext.pre = node;
        }
        private void afterRemove(Node node){
            Node pre = node.pre;
            Node next = node.next;
            pre.next = next;
            next.pre = pre;
        }
    }


    /**
     * 答案，哈希表 + 双向链表
     * 虚拟头尾
     * 他这里用了一个节点当value
     * 我和答案很像，但是耗时大太多，主要还是list的问题，list应该装value，这样从map里面get到value的时候，也就获得了list的节点
     */
    public class LRUCache2 {
        class DLinkedNode {
            int key;
            int value;
            DLinkedNode prev;
            DLinkedNode next;
            public DLinkedNode() {}
            public DLinkedNode(int _key, int _value) {key = _key; value = _value;}
        }

        private Map<Integer, DLinkedNode> cache = new HashMap<Integer, DLinkedNode>();
        private int size;
        private int capacity;
        private DLinkedNode head, tail;

        public LRUCache2(int capacity) {
            this.size = 0;
            this.capacity = capacity;
            // 使用伪头部和伪尾部节点
            head = new DLinkedNode();
            tail = new DLinkedNode();
            head.next = tail;
            tail.prev = head;
        }

        public int get(int key) {
            DLinkedNode node = cache.get(key);
            if (node == null) {
                return -1;
            }
            // 如果 key 存在，先通过哈希表定位，再移到头部
            moveToHead(node);
            return node.value;
        }

        public void put(int key, int value) {
            DLinkedNode node = cache.get(key);
            if (node == null) {
                // 如果 key 不存在，创建一个新的节点
                DLinkedNode newNode = new DLinkedNode(key, value);
                // 添加进哈希表
                cache.put(key, newNode);
                // 添加至双向链表的头部
                addToHead(newNode);
                ++size;
                if (size > capacity) {
                    // 如果超出容量，删除双向链表的尾部节点
                    DLinkedNode tail = removeTail();
                    // 删除哈希表中对应的项
                    cache.remove(tail.key);
                    --size;
                }
            }
            else {
                // 如果 key 存在，先通过哈希表定位，再修改 value，并移到头部
                node.value = value;
                moveToHead(node);
            }
        }

        private void addToHead(DLinkedNode node) {
            node.prev = head;
            node.next = head.next;
            head.next.prev = node;
            head.next = node;
        }

        private void removeNode(DLinkedNode node) {
            node.prev.next = node.next;
            node.next.prev = node.prev;
        }

        private void moveToHead(DLinkedNode node) {
            removeNode(node);
            addToHead(node);
        }

        private DLinkedNode removeTail() {
            DLinkedNode res = tail.prev;
            removeNode(res);
            return res;
        }
    }

    /**
     * 直接用LinkedHashMap
     */
    class LRUCache5 extends LinkedHashMap<Integer, Integer> {
        private int capacity;

        public LRUCache5(int capacity) {
            super(capacity, 0.75F, true);
            this.capacity = capacity;
        }

        public int get(int key) {
            return super.getOrDefault(key, -1);
        }

        public void put(int key, int value) {
            super.put(key, value);
        }

        @Override
        protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
            return size() > capacity;
        }
    }


    /**
     * 5，map+list
     * 还是list的访问耗时太大了，毕竟是遍历的
     */
    class LRUCache3 {

        private int capacity;
        // Integer的hashCode就是自己，不用担心同一个数值的Integer是不同对象的问题
        private Map<Integer, Integer> recordMap = new HashMap<>();

        private List<Integer> recordList = new ArrayList<>();

        public LRUCache3(int capacity) {
            this.capacity = capacity;
        }

        public int get(int key) {
            if(!recordMap.containsKey(key)){
                return -1;
            }
            int res = recordMap.get(key);
            recordList.remove((Integer)key);
            recordList.add(key);
            return res;
        }

        public void put(int key, int value) {
            if(recordMap.containsKey(key)){
                recordMap.put(key, value);
                recordList.remove((Integer)key);
                recordList.add(key);
            }else{
                if(recordList.size() == capacity){
                    Integer toRemove = recordList.get(0);
                    recordList.remove((Integer)toRemove);
                    recordMap.remove(toRemove);
                }
                recordMap.put(key, value);
                recordList.add(key);
            }
        }
    }

    /**
     * 7, 5
     * 问题很多，比如list是不去重的，map是去重的，用list去装key不可能。
     */
    class LRUCache {

        int capacity = 0;
        Map<String, String[]> cacheMap = new HashMap<>();
        String head = "head";
        String tail = "tail";

        public LRUCache(int capacity) {
            this.capacity = capacity;

            String[] headValue = new String[]{"", "", "tail"};
            cacheMap.put(head, headValue);
            String[] tailValue = new String[]{"", "head", ""};
            cacheMap.put(tail, tailValue);
        }

        public int get(int key) {
            String keyString = "" + key;
            if(!cacheMap.containsKey(keyString)){
                return -1;
            }
            // 把它放最后
            String[] curValue = cacheMap.get(keyString);
            int res = Integer.parseInt(curValue[0]);
            put(key, res);
            return res;
        }

        public void put(int key, int value) {
            String keyString = "" + key;

            // 存在则删除
            if(cacheMap.containsKey(keyString)){
                String[] curValues = cacheMap.get(keyString);
                cacheMap.get(curValues[1])[2] = curValues[2];
                cacheMap.get(curValues[2])[1] = curValues[1];
                cacheMap.remove(keyString);
            }
            // 现在肯定不存在了，新增到最后
            String[] tailValue = cacheMap.get(tail);
            String tailValuePreKey = tailValue[1];
            String[] tailValuePre = cacheMap.get(tailValuePreKey);
            tailValuePre[2] = keyString;
            tailValue[1] = keyString;
            cacheMap.put(keyString, new String[]{"" + value, tailValuePreKey, tail});
            // 超限的话，删除第一个
            if(cacheMap.size() > capacity + 2){
                String[] headValue = cacheMap.get(head);
                String[] firstValue = cacheMap.get(headValue[2]);
                cacheMap.remove(headValue[2]);
                headValue[2] = firstValue[2];
                cacheMap.get(firstValue[2])[1] = head;
            }
        }
    }


}
